#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@sharp>
#
# Distributed under terms of the MIT license.

"""

"""

from pprint import pprint


from collections import defaultdict

class DancingLink:
    def __init__(self, metrix):
        self.metrix = metrix
        self.rows = len(metrix)
        self.cols = len(metrix[0])

        self.row_sparse = defaultdict(set)
        self.col_sparse = defaultdict(set)
        self.sparse()

        pprint(self.row_sparse)
        pprint(self.col_sparse)

        pprint(self.metrix)
        self.run()

    def run(self):
        self.unhandled_cols = set( range(self.cols) )
        self.forbidden_rows = set()
        self.solution_path = []
        ret = self.try_rec()

        print('ret ', ret)
        print('solution ', self.solution_path)

    def try_rec(self):
        if len(self.unhandled_cols) == 0:
            return True

        if len(self.forbidden_rows) == self.rows:
            # 这个靠下面的逻辑也可以
            return False

        cur_handled_col = self.unhandled_cols.pop()
        cur_try_rows = self.col_sparse[cur_handled_col]
        print('try col', cur_handled_col)

        # for cur_try_row in cur_try_rows:
        #     if cur_try_row in self.forbidden_rows:      # 冲突行
        #         continue

        # 提前剔除所有冲突行:
        for cur_try_row in cur_try_rows.difference(self.forbidden_rows):
            print('   try row', cur_try_row, "of ", cur_handled_col)
            hit_rows, hit_cols = self.select_rows_and_cols(cur_try_row)

            # set
            origin_forbidden_rows = set(self.forbidden_rows)
            origin_unhandled_cols = set(self.unhandled_cols)

            self.forbidden_rows = self.forbidden_rows.union(hit_rows)
            assert self.unhandled_cols.union([cur_handled_col]).issuperset(hit_cols)

            self.unhandled_cols = self.unhandled_cols.difference(hit_cols)

            if self.try_rec():
                self.solution_path.append(cur_try_row)
                return True

            # clear/restore
            self.forbidden_rows = set(origin_forbidden_rows)
            self.unhandled_cols = set(origin_unhandled_cols)


        self.unhandled_cols.add(cur_handled_col)
        return False

    def select_rows_and_cols(self, row):
        selected_cols = self.row_sparse[row]
        # print("selected_cols", selected_cols)

        selected_rows = set()
        for c in selected_cols:
            selected_rows = selected_rows.union(self.col_sparse[c])
        # print("selected_rows", selected_rows)

        return selected_rows, selected_cols

    def sparse(self):
        for r in range( self.rows ):
            for c in range( self.cols ):
                if self.metrix[r][c] == 1:
                    self.row_sparse[r].add(c)
                    self.col_sparse[c].add(r)

def get_matrix():
    # l = [
    #     [0, 0, 1, 0, 1, 1, 0],
    #     [1, 0, 0, 1, 0, 0, 1],

    #     [0, 1, 1, 0, 0, 1, 0],
    #     [1, 0, 0, 1, 0, 0, 0],

    #     [0, 1, 0, 0, 0, 0, 1],
    #     [0, 0, 0, 1, 1, 0, 1],
    # ]

    l = [
        [0, 1, 0],
        [0, 0, 1],
        [1, 0, 0],
        [1, 1, 0],
        [0, 1, 1],
        [1, 1, 1],
    ]

    return l

def test():
    s = DancingLink(get_matrix())

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
